package com.gitee.algorithm.linear;

import java.util.Iterator;

public class LinkList<T> implements Iterable<T>{
    //记录头结点
    private Node head;

    //记录链表长度
    private int N;


    //节点类
    public class Node{
        //储存数据
        T item;
        //下一个节点
        Node next;

        //  构造方法
        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    //LinkList构造方法
    public  LinkList(){
        //初始化头结点
        this.head=new Node(null,null);
        //初始化链表长度
        this.N=0;
    }

    //清空链表
    public void clear(){
        head.next=null;
        this.N=0;
    }

    //获取链表长度
    public int length(){
        return N;
    }

    //判断链表是否为空
    public boolean isEmpty(){
        return N==0;
    }

    //获取指定位置i处的元素
    public T get(int i){
        //通过循环，从头结点找i次，就可以找到对应的元素值
        Node n=head.next;
        for(int index=0;index<i;index++){
            n=n.next;
        }
        return n.item;
    }

    //向链表中插入元素t
    public void  insert(T t){
        //找到当前最后一个节点
        Node n=head;
        while (n.next!=null){
            n=n.next;
        }
        //创建新节点
        Node newNode=new Node(t,null);
        //让当前最后一个节点指向新节点
        n.next=newNode;

        //元素个数加一
        N++;
    }

    //在指定i位置添加元素
    public void insert(int i,T t){
        //找到i前位置节点
        Node pre=head;
        for(int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i位置节点
        Node curr = pre.next;
        //创建新节点，新节点指向i位置节点
        Node newNode=new Node(t,curr);
        //让i位置前一个节点指向新节点
        pre.next=newNode;
        //链表长度加一
        N++;
    }

    //删除i位置节点,并返回被删除节点
    public T remove(int i){
        //找到i前处节点
        Node pre=head;
        for (int index=0;index<=i-1;index++){
            pre=pre.next;
        }
        //找到i处节点
        Node curr=pre.next;
        //找到i后一个位置节点
        Node nextNode=curr.next;
        //链表长度减一
        N--;
        //返回被删除节点
        return curr.item;
    }

    //查找处元素t在链表中第一次出现位置
    public int indexOf(T t){
        //从头结点开始，挨个取出item和t比较，如果相同就找到了
        Node n=head;
        for (int i=0;n.next!=null;i++){
            n=n.next;
            if(n.item.equals(t)){
                return i;
            }
        }
        return -1;
    }


    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    private class  LIterator implements Iterator{
        private Node n;
        public LIterator(){
            this.n=head;
        }
        @Override
        public boolean hasNext() {
            return n.next!=null;
        }

        @Override
        public Object next() {
            n=n.next;
            return n.item;
        }
    }

    //用来反转整个链表
    public void reverse(){
        //判断当前链表是否为空链表，如果为空链表，则结束否则调用重载reverse方法完成反转
        if (isEmpty()){
            return;
        }
        reverse(head.next);
    }
    //反转指定的结点curr,并返回反转后的结点
    public Node reverse(Node curr){
        if ( curr.next==null){
            head.next=curr;
            return curr;
        }
        //递归反转curr的下一个结点，返回值就是链表反转后，当前结点的上一个结点
        Node pre = reverse(curr.next);
        //让返回的结点的下一个结点变成当前结点curr
        pre.next=curr;
        //把当前结点的下一个结点变成null
        curr.next=null;
        return curr;
    }




}
